|
|
|
| Non-negative and Sparse Graph Construction Algorithm Based on Split Bregman Method |
| SHEN Ze-Fan, XU Lin-Li |
| School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027 |
|
|
|
|
Abstract In graph-based machine learning algorithms, the construction of the graph representing the data structure is the key issue. In this paper, a non-negative and sparse graph construction algorithm based on split Bregman method is presented. A weight matrix is learned by solving an equality formulation of the sparse representation through split Bregman method. In the weight matrix, each data sample can be represented by a non-negative linear combination of other samples. The constructed graph of the proposed algorithm can capture the linear relationship between data samples. Experimental results under semi-supervised learning framework demonstrate that the proposed algorithm can capture the latent structure information of data well.
|
|
Received: 25 March 2014
|
|
|
|
|
|
[1] Zhu X J, Ghahramani Z B, Lafferty J. Semi-supervised Learning Using Gaussian Fields and Harmonic Functions // Proc of the 20th International Conference on Machine Learning. Washington, USA, 2003: 912-919
[2] Zhou D Y, Bousquet O, Lal T N, et al. Learning with Local and Global Consistency[EB/OL].[2014-02-25]. http://papers.nips.cc/paper/2506-learning-with-local-and-global-consistency.pdf
[3] Roweis S T, Saul L K. Nonlinear Dimensionality Reduction by Locally Linear Embedding. Science, 2000, 290(5500): 2323-2326
[4] Yan S C, Wang H. Semi-supervised Learning by Sparse Representation // Proc of the SIAM International Conference on Data Mining. Sparks, USA, 2009: 792-801
[5] Cheng B, Yang J C, Yan S C, et al. Learning with l1-Graph for Image Analysis. IEEE Trans on Image Processing, 2010, 19(4): 858-866
[6] Zhuang L S, Gao H Y, Lin Z C, et al. Non-negative Low Rank and Sparse Graph for Semi-supervised Learning // Proc of the IEEE Conference on Computer Vision and Pattern Recognition. Providence, USA, 2012: 2328-2335
[7] Liu G C, Lin Z C, Yu Y. Robust Subspace Segmentation by Low-Rank Representation // Proc of the 27th International Conference on Machine Learning. Haifa, Israel, 2010: 663-670
[8] Szlam A, Guo Z H, Osher S. A Split Bregman Method for Non-ne-gative Sparsity Penalized Least Squares with Applications to Hyperspectral Demixing // Proc of the 17th IEEE International Conference on Image Processing. Hong Kong, China, 2010: 1917-1920
[9] Yin W T, Osher S, Goldfarb D, et al. Bregman Iterative Algorithms for l1-Minimization with Applications to Compressed Sensing. SIAM Journal on Imaging Sciences, 2008, 1(1): 143-168
[10] Osher S, Mao Y, Dong B, et al. Fast Linearized Bregman Iteration for Compressive Sensing and Sparse Denoising. Communications in Mathematical Sciences, 2010, 8(1): 93-111
[11] Goldstein T, Osher S. The Split Bregman Method for l1-Regula-rized Problems. SIAM Journal on Imaging Sciences, 2009, 2(2): 323-343 |
|
|
|
2015, Vol. 28 
